import java.util.*;

public class Main {
    public static void main(String[] args) {
        CFG cfg = new CFG(); // 生成式集合
        ArrayList<Character> T = new ArrayList<Character>(); // 终结符
        ArrayList<Character> N = new ArrayList<Character>(); // 非终结符
        cfg.readCFG(T, N);
        cfg.ungenerated(N, T);
        cfg.unavailable(N, cfg.get(0).left);
        cfg.remove1e(N);
        cfg.removeEpt();
        cfg.ungenerated(N, T);
        cfg.unavailable(N, cfg.get(0).left);
        cfg.printCFG();
        return;
    }
}

class CFG extends ArrayList<Function> {
    public void readNandT(Scanner in, ArrayList<Character> al) {
        // 读取一行的字符，用于读取终结符与非终结符集合
        String str = in.nextLine();
        while (!str.equals("")) {
            int index = str.indexOf(" ");
            if (index >= 0) {
                String current = str.substring(0, index);
                if (!current.equals(""))
                    al.add(current.charAt(0));
                str = str.substring(index + 1);
            } else {
                al.add(str.charAt(0));
                break;
            }
        }
    }

    public void readCFG(ArrayList<Character> T, ArrayList<Character> N) {
        // 从控制台读取上下文无关文法，其格式为统一左部生成式写一行，如：S-->a|AB 写为S a AB
        // 第一行为生成式行数，第二行为非终结符集合，第三行为终结符，第四行开始为生成式，默认S为起始符,空字符为e，生成式第一行为S
        // N保留作为新的开始符号，保留e表示ε
        int number;
        Scanner in = new Scanner(System.in);
        number = in.nextInt();
        in.nextLine();
        this.readNandT(in, N);
        this.readNandT(in, T);
        for (int i = 1; i <= number; i++) {
            Function current = new Function();
            current.readFunction(in);
            this.add(current);
        }
        in.close();
        return;
    }

    public void printCFG() {
        int size = this.size();
        System.out.println("---------------------------");
        for (int i = 0; i <= size - 1; i++) {
            Function current = this.get(i);
            System.out.print(current.left + "-->" + current.right.get(0));
            int rightSize = current.right.size();
            for (int i0 = 1; i0 <= rightSize - 1; i0++)
                System.out.print("|" + current.right.get(i0));
            System.out.println("");
        }
        System.out.println("---------------------------");
        return;
    }

    public void deleteFunc(ArrayList<Character> keep, ArrayList<Character> N) {
        // 删除不可达与非产生符号，keep中为有用的符号
        ArrayList<Character> E = (ArrayList<Character>) N.clone();
        int ksize = keep.size(), esize = N.size() - ksize;
        for (int i = 0; i <= ksize - 1; i++)
            E.remove(keep.get(i));
        for (int i = 0; i <= esize - 1; i++)
            N.remove(E.get(i));
        for (int i0 = 0; i0 <= this.size() - 1; i0++) {
            Function current = this.get(i0);
            for (int i1 = 0; i1 <= esize - 1; i1++) {
                Character ecurrent = E.get(i1);
                if (current.left == ecurrent) {
                    this.remove(i0);
                    break;
                }
            }
        }
        for (int i0 = 0; i0 <= this.size() - 1; i0++) {
            Function current = this.get(i0);
            current.deleteE(E);
            if (current.right.size() == 0) {
                this.remove(i0);
                i0 = i0 - 1;
            }
        }
        return;
    }

    public void unavailable(ArrayList<Character> N, Character beginning) {
        // 删除不可达的元素
        int cfgsize = this.size();
        ArrayList<Character> N1 = new ArrayList<Character>();
        N1.add(beginning);
        while (true) {
            int  newe = 0;
            for (int i0 = 0; i0 <= N1.size() - 1; i0++) {
                Character n1current = N1.get(i0);
                for (int i1 = 0; i1 <= cfgsize - 1; i1++) {
                    Function fcurrent = this.get(i1);
                    if (fcurrent.left == n1current) {
                        int rightsize = fcurrent.right.size();
                        for (int i2 = 0; i2 <= rightsize - 1; i2++) {
                            String rightcurrent = fcurrent.right.get(i2);
                            int length = rightcurrent.length();
                            for (int i3 = 0; i3 <= length - 1; i3++) {
                                if (N.indexOf(rightcurrent.charAt(i3)) != -1
                                        && N1.indexOf(rightcurrent.charAt(i3)) == -1)
                                    N1.add(rightcurrent.charAt(i3));
                            }
                        }
                        break;
                    }
                }
            }
            if (newe == 0)
                break;
        }
        this.deleteFunc(N1, N);
        return;
    }

    public void ungenerated(ArrayList<Character> N, ArrayList<Character> T) {
        // 删除非产生的符号
        // 为简化程序，先将终结符写入产生符号的集合，求解完成再去掉
        ArrayList<Character> N1 = (ArrayList<Character>) T.clone();
        N1.add('e');
        int cfgsize = this.size(), Tsize = T.size();
        while (true) {
            int newe = 0;
            for (int i0 = 0; i0 <= cfgsize - 1; i0++) {
                Function fcurrent = this.get(i0);
                int rightsize = fcurrent.right.size();
                for (int i1 = 0; i1 <= rightsize - 1; i1++) {
                    String rcurrent = fcurrent.right.get(i1);
                    int length = rcurrent.length(), is_N1 = 1;
                    for (int i2 = 0; i2 <= length - 1; i2++) {
                        if (N1.indexOf(rcurrent.charAt(i2)) == -1) {
                            is_N1 = 0;
                            break;
                        }
                    }
                    if (is_N1 == 1 && N1.indexOf(fcurrent.left) == -1) {
                        N1.add(fcurrent.left);
                        newe++;
                        break;
                    }
                }
            }
            if (newe == 0)
                break;
        }
        for (int i = 0; i <= Tsize; i++)
            N1.remove(0);
        this.deleteFunc(N1, N);
        return;
    }

    public void remove1e(ArrayList<Character> N) {
        // 消去单产生式,先从推导式开始得到所有的有单生成式的非终结符，再从后往前消去单生成式
        ArrayList<Character> stack = new ArrayList<Character>();
        stack.add('S');
        CFG cfg1 = (CFG) this.clone();
        for (int i0 = 0; i0 <= stack.size() - 1; i0++) {
            for (int i1 = 0; i1 <= cfg1.size() - 1; i1++) {
                Function fcurrent = cfg1.get(i1);
                if (fcurrent.left == stack.get(i0)) {
                    int rightsize = fcurrent.right.size();
                    for (int i2 = 0; i2 <= rightsize - 1; i2++) {
                        String rcurrent = fcurrent.right.get(i2);
                        if (rcurrent.length() == 1 && N.indexOf(rcurrent.charAt(0)) != -1)
                            stack.add(rcurrent.charAt(0));
                    }
                    cfg1.remove(i1);
                }
            }
        }
        int stacksize = stack.size(), cfgsize = this.size();
        for (int i0 = stacksize - 1; i0 >= 0; i0--) {
            for (int i1 = 0; i1 <= cfgsize - 1; i1++) {
                Function fcurrent = this.get(i1);
                if (fcurrent.left == stack.get(i0)) {
                    for (int i2 = 0; i2 <= fcurrent.right.size() - 1; i2++) {
                        String rcurrent = fcurrent.right.get(i2);
                        if (rcurrent.length() == 1 && N.indexOf(rcurrent.charAt(0)) != -1) {
                            for (int i3 = 0; i3 <= cfgsize - 1; i3++) {
                                Function fcurrent1 = this.get(i3);
                                if (fcurrent1.left == rcurrent.charAt(0)) {
                                    int rightsize1 = fcurrent1.right.size();
                                    for (int i4 = 0; i4 <= rightsize1 - 1; i4++) {
                                        String rcurrent1 = fcurrent1.right.get(i4);
                                        if (!rcurrent1.equals(fcurrent.left + "")
                                                && fcurrent.right.indexOf(rcurrent1) == -1)
                                            fcurrent.right.add(rcurrent1);
                                    }
                                }
                            }
                            fcurrent.right.remove(i2);
                            i2 = i2 - 1;
                        }
                    }
                    stack.remove(i0);
                    break;
                }
            }
        }
    }

    public void removeEpt() {
        // 消去含e产生式
        int if_S_has_Ept = 0;
        ArrayList<Character> N1 = new ArrayList<Character>();
        N1.add('e');
        while (N1.size() > 0) {
            ArrayList<Character> newN1 = new ArrayList<Character>();
            for (int i0 = 0; i0 <= N1.size() - 1; i0++) {
                for (int i1 = 0; i1 <= this.size() - 1; i1++) {
                    if (this.get(i1).removeEptE(N1) == 1) {
                        newN1.add(this.get(i1).left);
                        if (i1 == 0)
                            if_S_has_Ept = 1;
                    }
                }
            }
            N1 = newN1;
        }
        if (if_S_has_Ept == 1) {
            Function S1 = new Function();
            S1.left = 'N';
            S1.right = (ArrayList<String>) this.get(0).right.clone();
            S1.right.add("e");
            this.add(0, S1);
        }
        return;
    }
}

class Function {
    Character left;
    ArrayList<String> right = new ArrayList<String>();

    public void readFunction(Scanner in) {
        // 读取同一个左部的生成式
        this.left = in.next().charAt(0);
        String str = in.nextLine();
        while (!str.equals("")) {
            int index = str.indexOf(" ");
            if (index >= 0) {
                String current = str.substring(0, index);
                if (!current.equals("") && !str.equals(left + ""))
                    this.right.add(current);
                str = str.substring(index + 1);
            } else {
                if (!str.equals(left + ""))
                    this.right.add(str);
                break;
            }
        }
        return;
    }

    public void deleteE(ArrayList<Character> E) {
        // 删除生成式右端无用的元素
        int ESize = E.size();
        for (int i0 = 0; i0 <= this.right.size() - 1; i0++) {
            String current = this.right.get(i0);
            for (int i1 = 0; i1 <= ESize - 1; i1++) {
                Character e = E.get(i1);
                if (current.indexOf(e) != -1) {
                    right.remove(i0);
                    i0 = i0 - 1;
                }
            }
        }
        return;
    }

    public int removeEptE(ArrayList<Character> E) {
        // 去掉生成式中的e，若这个生成式最终也包含e，返回1，否则返回0
        int ESize = E.size(), has_ept = 0;
        for (int i0 = 0; i0 <= this.right.size() - 1; i0++) {
            String current = this.right.get(i0);
            for (int i1 = 0; i1 <= ESize - 1; i1++) {
                Character e = E.get(i1);
                int csize = current.length();
                for (int i2 = 0; i2 <= csize - 1; i2++) {
                    if (current.charAt(i2) == e) {
                        if(e=='e'){
                            this.right.remove(i0);
                            i0--;
                            has_ept = 1;
                            break;
                        }
                        String newe = "";
                        if (i2 > 0)
                            newe = current.substring(0, i2) + newe;
                        if (i2 < csize - 1)
                            newe = newe + current.substring(i2 + 1);
                        if (newe.length() == 0)
                            has_ept = 1;
                        else {
                            if (this.right.indexOf(newe) == -1)
                                this.right.add(newe);
                        }
                    }
                }
            }
        }
        return has_ept;
    }
}